package com.lw.leetcode.sort.c;

import java.util.ArrayList;
import java.util.List;
import java.util.TreeMap;

/**
 * Created with IntelliJ IDEA.
 * 699. 掉落的方块
 *
 * @author liw
 * @version 1.0
 * @date 2022/5/26 9:06
 */
public class FallingSquares {


    public static void main(String[] args) {
        FallingSquares test = new FallingSquares();

        // [2, 5, 5]
//        int[][] arr = {{1, 2}, {2, 3}, {6, 1}};

        // [100, 100]
//        int[][] arr = {{100, 100}, {200, 100}};

        // [667775,967539,967539,1243092,1243092,1243092,1243092,1243092,1243092,1243092,1243092,1243092,1243092,1243092,1243092,1243092,1243092,1243092,1702441,1702441]
        int[][] arr = {{83959861, 667775}, {33716237, 967539}, {92605138, 655553}, {34167465, 275553}, {47050483, 622231}, {90011402, 655094}, {53460666, 289184}, {38326063, 879534}, {1135628, 29950}, {63668338, 227557}, {76092089, 507075}, {35545928, 797893}, {55538160, 108461}, {14796554, 202551}, {73356376, 757480}, {66304222, 142983}, {85870633, 289247}, {56205037, 632383}, {34457684, 734902}, {30582666, 917386}};

        List<Integer> list = test.fallingSquares(arr);
        System.out.println(list);
    }

    public List<Integer> fallingSquares(int[][] positions) {
        int length = positions.length;
        List<Integer> list = new ArrayList<>(length);
        int max = 0;
        TreeMap<Integer, Long> map = new TreeMap<>();
        for (int[] position : positions) {
            int st = position[0];
            long h = 0;
            Integer key = map.floorKey(st);
            int end = st + position[1] - 1;
            if (key != null) {
                long value = map.get(key);
                if ((int) value >= st) {
                    map.put(key, value - (int) value + st - 1);
                    h = Math.max(h, (int) (value >> 32));
                }
                if ((int) value > end) {
                    map.put(end + 1, value);
                }
            }
            key = map.ceilingKey(st);
            while (key != null && key <= end) {
                long value = map.get(key);
                map.remove(key);
                h = Math.max(h, (int) (value >> 32));
                if ((int) value > end) {
                    map.put(end + 1, value);
                }
                key = map.ceilingKey(st);
            }
            h += position[1];
            max = Math.max(max, (int) h);
            map.put(st, (h << 32) + end);
            list.add(max);
        }
        return list;
    }

}
